package wjl.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * 无重复字符的最长子串:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 
 * @author Wjl
 *
 */
public class LengthOfLongestSubstring {
    public static void main( String[] args ) {
        System.out.println( lengthOfLongestSubstring2( "tmmzuxt" ) );
    }

    /*
     * 双指针
     */
    public static int lengthOfLongestSubstring1( String s ) {
        if ( s == null ){
            return 0;
        }
        int len = s.length();
        if ( len <= 1 ){
            return len;
        }
        int            x   = 0;
        int            y   = 1;
        int            max = 1;
        Set<Character> set = new HashSet<>();
        set.add( s.charAt( x ) );
        while (x < y && y < len){
            set.add( s.charAt( y ) );
            if ( set.size() == y - x + 1 ){
                max = Math.max( max, set.size() );
                y++;
            } else{
                if ( s.charAt( x ) != s.charAt( y ) ){
                    set.remove( s.charAt( x ) );
                    x++;
                } else{
                    x++;
                    y++;
                }
            }
        }
        return max;
    }

    /*
     * 错误方法
     */
    public static int lengthOfLongestSubstring2( String s ) {
        if ( s == null ){
            return 0;
        }
        int len = s.length();
        if ( len <= 1 ){
            return len;
        }
        int max = 0;
        if ( s.substring( 0, s.length() - 1 )
                .indexOf( String.valueOf( s.charAt( s.length() - 1 ) ) ) == -1 ){
            max = lengthOfLongestSubstring1( s.substring( 0, s.length() - 1 ) ) + 1;
        } else{
            max = lengthOfLongestSubstring1( s.substring( 0, s.length() - 1 ) );
        }
        return max;
    }
}
